/**
 * 最长公共子序列
 * @param {string} text1
 * @param {string} text2
 * @return {number}
 */
var longestCommonSubsequence = function (text1, text2) {
  // console.log(text1, text2);
  let x = text1.length - 1;
  let y = text2.length - 1;
  if (!text1 || !text2) {
    return 0;
  }
  if (text1.charAt(x) === text2.charAt(y)) {
    return longestCommonSubsequence(text1.substring(0, x), text2.substring(0, y)) + 1;
  } else {
    return Math.max(longestCommonSubsequence(text1, text2.substring(0, y)), longestCommonSubsequence(text1.substring(0, x), text2));
  }
};

// "pmjghexybyrgzczy"
// "hafcdqbgncrcbihkd"

var longestCommonSubsequence2 = function (text1, text2) {
  // text1 = ' ' + text1;
  // text2 = ' ' + text2;
  let x = text1.length;
  let y = text2.length;
  // 构建动态规划表格
  let lcs = new Array(x + 1).fill(0);
  let i, j;
  for (i = 0; i < lcs.length; i++) {
    lcs[i] = new Array(y + 1).fill(0);
  }
  console.log(lcs, text1, text2)
  for (i = 0; i <= x; i++) {
    for (j = 0; j <= y; j++) {
      if (i === 0 || j === 0) {
        lcs[i][j] = 0;
      } else if (text1[i - 1] === text2[j - 1]) {
        lcs[i][j] = lcs[i - 1][j - 1] + 1;
      } else {
        lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
      }
    }
  }
  console.log(lcs)
  return lcs[x][y];
}

console.log(longestCommonSubsequence2('abc', 'def'));